1. Field of the Invention
The present invention relates to a method, data processing system and computer program for comparing floating point numbers.
2. Description of the Prior Art
It is common for data processing systems to be required to perform various floating point computations on data. To ensure that a consistent approach was adopted in the way in which floating point computations are handled by various data processing systems, a standard was produced in 1985 called the xe2x80x9cIEEE Standard for Binary Floating-Point Arithmeticxe2x80x9d, ANSI/IEEE Standard 754-1985, the Institute of Electrical and Electronic Engineers, Inc., New York, 10017 (hereafter referred to as the IEEE754-1985 Standard).
Performing comparisons of floating point numbers in accordance with the IEEE754-1985 Standard is non-trivial as there are a number of exception conditions which need to be identified, in order that appropriate exception routines can be applied to deal with such exception conditions. One example of such an exception condition is where one or more of the floating point numbers being compared are NaNs (Not a Number). It is clear that, irrespective of whether the comparison is performed in hardware or software, the time taken to determine whether such exception conditions exist will impact on the efficiency of the comparison process. For example, assuming a software approach, a generic check that detects whether either of two floating point numbers are NaNs takes 6 cycles, as illustrated by the following instruction sequence:
The MOV instruction stores the number 0xc3x97FFE00000 in the register tmp. The CMP instruction then compares the value of the first floating point number, shifted left by one position, with the number stored in the register tmp. In the embodiment to which the above instruction sequence relates, a floating point number is represented by a mantissa value, an exponent value, and a sign bit indicating whether the number is positive or negative, in double precision mode these three values comprising a total of 64 bits, with the top 32 bits including the sign bit, followed by the exponent, followed by the first part of the mantissa. Accordingly, the CMP instruction compares the top 32 bits of the first floating point number, shifted left by one to remove the sign bit, with the number stored in the register tmp, and thus it can be seen that this instruction compares the exponent of the first floating point number with the number stored in the register tmp.
A NaN shifted left by one will have a value greater than FFE00000 00000000. Hence, if the result of the first comparison is HI, i.e. the top 32 bits of the first floating point number shifted left by one was greater than FFE00000, this clearly indicates the presence of an NaN.
However, if the result of this first comparison was equal (i.e. the top 32 bits of the first floating point number shifted left by one was FFE00000), the instruction CMPEQ then compares the bottom 32 bits of the first floating point number with the number 0, since it is still possible that the first floating point number may be a NaN. Hence, if a HI signal is produced by either the first or second comparison, then this indicates that the first floating point number is a NaN.
If the result of the previous two comparisons were less than or equal, and hence an NaN was determined not to be present, the next two instructions then perform a similar comparison for the second floating point number, again a high signal indicating that a NaN has been found. The final instruction then branches to an exception routine called NaN_lab if a high signal has been produced.
It will be appreciated that the performance of such a check as part of each floating point compare operation introduces a significant overhead, and adversely affects the efficiency of the compare operation. It is an object of the present invention to alleviate this overhead.
Viewed from a first aspect, the present invention provides a method of comparing first and second floating point numbers to generate a result indicative of the comparison unless one or more exception conditions exist, comprising the steps of: (a) providing a hierarchy of tests arranged to identify from said first and second floating point numbers whether said one or more exception conditions exist, a first test in said hierarchy predicting whether said one or more exception conditions may exist, and each subsequent test in the hierarchy being arranged to determine with more accuracy than the previous test whether said one or more exception conditions exist, each test being arranged to generate a hit signal if that test predicts that said one or more exception conditions exist; (b) executing the first test in said hierarchy; (c) if the executed test does not generate a hit signal, branching to a compare function, and executing the compare function to generate the result indicative of the comparison of the first and second floating point numbers; (d) if the executed test generates a hit signal and is not a final test in the hierarchy, performing the steps of: (d)(i) branching to the next test in the hierarchy; (d) (ii) executing the test branched to at said step (d)(i); and (d)(iii) returning to said step (c); (e) if the executed test generates a hit signal and is the final test in the hierarchy, generating an exception signal indicating the presence of said one or more exception conditions.
In accordance with the present invention, a hierarchy of tests are provided to predict the presence of one or more exception conditions. The first test predicts whether the one or more exception conditions may exist, and preferably is a xe2x80x9ccatch allxe2x80x9d test that identifies any situations where the one or more exception conditions may exist, including ones which ultimately may not give rise to an exception condition. If the test indicates that one or more exception conditions may exist, then a hit signal is generated and the method branches to a next test in the hierarchy, which is arranged to determine with more accuracy than the previous test whether said one or more exception conditions exist. Each time the hit signal is generated by a test, the process branches to the next, more accurate, test in the hierarchy, unless the test is the final test in the hierarchy, at which point an exception signal is generated to indicate the presence of said one or more exception conditions.
The benefit of this approach is that as soon as one of the tests does not produce a hit signal, i.e. the test has determined that the one or more exception conditions do not exist, the process can branch immediately to a compare function in order to generate a result indicative of the comparison of the first and second floating point numbers.
Generally speaking, the more accurate the test, the longer than test will take to perform, and accordingly the earlier tests in the hierarchy can be performed significantly quicker than a precise test which identifies definitely whether the one or more exception conditions exist. Accordingly, assuming that exception conditions occur relatively infrequently, it will be appreciated that the method of the present invention will enable most compare operations to branch relatively quickly to the compare function, without needing to perform more precise checks provided later in the hierarchy. Hence, such an approach significantly improves the efficiency of floating point comparisons over the known prior art software techniques.
In preferred embodiments, the hierarchy of tests includes a choice of first tests, each first test having subsequent tests dependent thereon, and the method further comprises the steps of, prior to said step (b): (i) determining whether either the first or second floating point number is negative; (ii) branching to a positive number first test if both the first and second floating point numbers are positive; (iii) branching to a negative number first test if either the first or second floating point number is negative.
It will be appreciated that the process for selecting a first test from a choice of first tests could be performed in any appropriate manner. For example, the method may instead comprise the steps of, prior to said step (b): (i) determining whether either the first or second floating point number is positive; (ii) branching to a negative number first test if both the first and second floating point numbers are negative; (iii) branching to a positive number first test if either the first or second floating point number is positive.
In preferred embodiments of the present invention, floating point numbers are represented by a sign bit, an exponent value, and a mantissa value. Both the exponent and mantissa are positive numbers. If the exponent of one floating point number is larger than the exponent of the other floating point number, then that number is larger. If the two exponent values are the same, then the floating point number with the larger mantissa will be the larger number. Accordingly, it will be appreciated that such floating point numbers behave like sign-magnitude numbers. Therefore, the exponent and mantissa can be compared together, rather than being separated.
Further, in preferred embodiments, it has been realised that unsigned comparisons can be used on sign-magnitude values, as illustrated by the following table:
Accordingly, it was realised that in preferred embodiments only two cases need to be considered, namely the case where both numbers are positive, or the case where at least one or the numbers is negative. Hence, this is why in preferred embodiments a preliminary step is performed to determine whether either the first or second floating point number is negative, and to branch to an appropriate first test dependent on that determination.
In preferred embodiments, each floating point number includes a sign bit indicating whether the number is positive or negative, and said step (i) comprises the steps of: performing a logical operation on the first and second floating point numbers to produce a combined value; and determining from the sign bit of the combined value whether either the first or second floating point number is negative. More particularly, in preferred embodiments, the sign bit of each floating point number is set to a logic 0 value for a positive number and a logic 1 value for a negative number, and said logical operation is a logical OR operation performed on the first and second floating point numbers. Accordingly, it will be appreciated that, in this embodiment, if the sign bit of the combined value is at a logic 1 value, then at least one of the floating point numbers is a negative number.
In preferred embodiments, both the positive number first test and the negative number first test involve predicting from said combined value whether said one or more exception conditions may exist. As an example of these first tests, consider a situation where the exception condition to be determined is the situation where either the first or second floating point number is a NaN. In such instances, a large exponent would be expected, and accordingly the first test would preferably merely involve determining whether the exponent of the combined value exceeded a predetermined number.
In preferred embodiments, a second test branched to from the first test is arranged to apply separate tests to both the first and second floating point numbers to produce a more accurate prediction than was obtained from the first test using the combined value. Accordingly, having regard to the earlier mentioned example of looking for a NaN, the second test may apply a similar test to each floating point number separately as was applied in the first test to the combined value, in order to remove any xe2x80x9cmiss-hitsxe2x80x9d resulting from the fact that the first test was looking merely at the combined value.
Further, in preferred embodiments, the final test in the hierarchy is arranged to apply a precise test to both the first and second floating point numbers to identify whether said one or more exception conditions do exist. Hence, having regard to the example of looking for a NaN, any appropriate precise test may be performed at this point if the process proceeds as far as the final test. As mentioned earlier, it is expected that the presence of such exception conditions will be rare, and that accordingly it will be rare for the method of the present invention to get as far as the final test in the hierarchy without branching to the compare function, and that accordingly the overall efficiency of the compare process will be improved.
Further, it will be appreciated that in some embodiments, the final test need not be a precise test, but that rather it may still include some xe2x80x9cmiss-hitsxe2x80x9d when generating a hit signal. The exception handling code branched to as a result of the exception signal would then handle these xe2x80x9cmiss-hitsxe2x80x9d in addition to handling any true exception conditions. Even though the exception handling code will be invoked more often than it needs to be, the process may still be efficient, assuming a hit signal from the final test is rare.
It will be appreciated that the method of the present invention can be used to predict a number of different exception conditions. However, as mentioned earlier, in preferred embodiments the one or more exception conditions comprise either the first or second floating point number being a NaN.
In one embodiment, the method of the present invention may be arranged to compare whether the first floating point number is less than the second floating point number, the compare function comprising a first comparison operation used if both the first and second floating point numbers are positive, and a second comparison operation used if either the first or second floating point numbers are negative.
Furthermore, in preferred embodiments, the first and second comparison operations are arranged to directly produce as their result a number of flags indicating the result of the comparison. This is possible as a result of the way in which either the first compare function or second compare function is invoked through branching from an appropriate point in the hierarchy of tests, and avoids the typical prior art requirement of having to set the flags during additional cycles following the end of the comparison process.
Viewed from a second aspect, the present invention provides a data processing system for comparing first and second floating point numbers to generate a result indicative of the comparison unless one or more exception conditions exist, comprising: a storage for storing a hierarchy of tests arranged to identify from said first and second floating point numbers whether said one or more exception conditions exist, a first test in said hierarchy predicting whether said one or more exception conditions may exist, and each subsequent test in the hierarchy being arranged to determine with more accuracy than the previous test whether said one or more exception conditions exist, each test being arranged to generate a hit signal if that test predicts that said one or more exception conditions exist; a processor for executing the first test in said hierarchy; if the executed test does not generate a hit signal, the processor being arranged to branch to a compare function, and to execute the compare function to generate the result indicative of the comparison of the first and second floating point numbers; if the executed test generates a hit signal and is not a final test in the hierarchy, the processor being arranged to branch to the next test in the hierarchy and to execute that next test; if the executed test generates a hit signal and is the final test in the hierarchy, the processor being arranged to generate an exception signal indicating the presence of said one or more exception conditions; the processor being arranged to work trough the tests in the hierarchy until either the compare function is executed, or the exception signal is generated.
Viewed from a third aspect, the present invention provides a computer program for configuring a data processing system to perform a method of comparing first and second floating point numbers to generate a result indicative of the comparison unless one or more exception conditions exist, the method comprising the steps of: (a) providing a hierarchy of tests arranged to identify from said first and second floating point numbers whether said one or more exception conditions exist, a first test in said hierarchy predicting whether said one or more exception conditions may exist, and each subsequent test in the hierarchy being arranged to determine with more accuracy than the previous test whether said one or more exception conditions exist, each test being arranged to generate a hit signal if that test predicts that said one or more exception conditions exist; (b) executing the first test in said hierarchy; (c) if the executed test does not generate a hit signal, branching to a compare function, and executing the compare function to generate the result indicative of the comparison of the first and second floating point numbers; (d) if the executed test generates a hit signal and is not a final test in the hierarchy, performing the steps of: (d)(i) branching to the next test in the hierarchy; (d)(ii) executing the test branched to at said step (d)(i); and (d)(iii) returning to said step (c); (e) if the executed test generates a hit signal and is the final test in the hierarchy generating an exception signal indicating the presence of said one or more exception conditions.
Viewed from a fourth aspect, the present invention provides a computer program product on a computer readable medium comprising a computer program in accordance with the third aspect of the present invention.